#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 初始化二叉树
TreeNode* initTree() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    return root;
}

// 前序遍历
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    cout << root->val << " ";
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

// 中序遍历
void inOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

// 后序遍历
void postOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    cout << root->val << " ";
}

// 插入节点
TreeNode* insertNode(TreeNode* root, int val) {
    if (root == NULL) return new TreeNode(val);
    if (val < root->val) root->left = insertNode(root->left, val);
    else root->right = insertNode(root->right, val);
    return root;
}

// 删除节点
TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == NULL) return root;
    if (val < root->val) root->left = deleteNode(root->left, val);
    else if (val > root->val) root->right = deleteNode(root->right, val);
    else {
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        TreeNode* temp = root->right;
        while (temp->left!= NULL) temp = temp->left;
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

// 查找节点
TreeNode* searchNode(TreeNode* root, int val) {
    if (root == NULL || root->val == val) return root;
    if (val < root->val) return searchNode(root->left, val);
    else return searchNode(root->right, val);
}

// 释放二叉树内存
void freeTree(TreeNode* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

// 计算二叉树高度
int treeHeight(TreeNode* root) {
    if (root == NULL) return 0;
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

// 主函数
int main() {
    TreeNode* root = initTree();
    cout << "初始化后的二叉树: ";
    preOrderTraversal(root);
    cout << endl;

    cout << "前序遍历: ";
    preOrderTraversal(root);
    cout << endl;

    cout << "中序遍历: ";
    inOrderTraversal(root);
    cout << endl;

    cout << "后序遍历: ";
    postOrderTraversal(root);
    cout << endl;

    root = insertNode(root, 6);
    cout << "插入节点 6 后的二叉树: ";
    preOrderTraversal(root);
    cout << endl;

    root = deleteNode(root, 2);
    cout << "删除节点 2 后的二叉树: ";
    preOrderTraversal(root);
    cout << endl;

    TreeNode* node = searchNode(root, 5);
    if (node!= NULL) cout << "找到了节点 5" << endl;
    else cout << "未找到节点 5" << endl;

    cout << "二叉树的高度: " << treeHeight(root) << endl;

    freeTree(root);
    return 0;
}
